/**
 * @file 027.回文链表.cc
 * @author snow-tyan (zziywang@163.com)
 * @brief {Life is too short to learn cpp.}
 * @version 0.1
 * @date 2021-11-17
 * 
 * @copyright Copyright (c) 2021
 * 
 */

#include <iostream>
#include <string>
#include <vector>
using namespace std;

struct ListNode {
    ListNode(int val = 0, ListNode *next = nullptr)
        : val(val), next(next) {}
    int val;
    ListNode *next;
};

class Solution
{
public:
    bool isPalindrome(ListNode *head)
    {
        // 想法一：存入数组，双指针回文判断 O(2N) O(N)
        // 想法二：快慢指针，先找到中点，然后reverse后半段，逐个比对 O(2.5N) O(1)
        // 破坏了原链表，就不恢复了...
        if (!head || !head->next) {
            return true;
        }
        ListNode *slow = head, *fast = head;
        while (fast->next && fast->next->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        ListNode *cur = slow->next, *pre = nullptr;
        while (cur) {
            ListNode *post = cur->next;
            cur->next = pre;
            pre = cur;
            cur = post;
        }
        // pre现在是链表头
        while (pre) {
            if (pre->val != head->val) {
                return false;
            }
            pre = pre->next;
            head = head->next;
        }
        return true;
    }
};